// n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
// 给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
// 每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
// 不能同行
// 不能同列
// 不能同斜线
function solveNQueens(n) {
    let result = []
    let chessboard = new Array(n).fill(0).map(_ => new Array(n).fill('.'))
    function backtracking(row) {
        if (row === n) {
            result.push(chessboard.map(item => item.join('')))
            return
        }
        for (let col = 0; col < n; col++) {
            if (isValid(chessboard, row, col)) {
                chessboard[row][col] = 'Q'
                backtracking(row + 1)
                chessboard[row][col] = '.'
            }            
        }
    }
    function isValid(chessboard, row, col) {
        for (let i = 0; i < row; i++) {
            if (chessboard[i][col] === 'Q') {
                return false
            }            
        }
        let i = row - 1
        let j = col - 1
        while (i >= 0 && j >= 0) {
            if (chessboard[i][j] === 'Q') {
                return false
            }
            i--
            j--
        }
        i = row - 1
        j = col + 1
        while (i >= 0 && j < n) {
            if (chessboard[i][j] === 'Q') {
                return false
            }
            i--
            j++
        }
        return true
    }
    backtracking(0)
    return result
}

console.log(solveNQueens(8))